package Euclid;

/**
 * Copyright (C), 2020-2020, XXX有限公司
 * FileName: Euclid
 * Author:   cakin
 * Date:     2020/1/6
 * Description: 计算两个非负数p和q的最大公约数：若q=0，则最大公约数为p。否则，将p除以q得到余数r，p和q的最大公约数即为q和r的最大公约数
 * 18和8的最大公约数：
 * 第一次递归：p=18，q=8:r=18%8=2，所以18和8的最大公约数为8和2的最大公约数
 * 第二次递归：p=8,q=2:r=8%2=0,最大公约数为2和0的最大公约数
 * 第三次递归：p=2，q=0，得到最大公约数为2
 */
public class Euclid {
    public static void main( String[] args ) {
        System.out.println(gcd(8,18));
    }
    public static int gcd(int p,int q){
        if(q==0){
            return p;
        }
        int r = p %q;
        return gcd(q,r);
    }
}
